/*
 * @lc app=leetcode.cn id=122 lang=golang
 *
 * [122] 买卖股票的最佳时机 II
 */

// 3. 动态规划
// dp[i][j] i代表第几天，j代表这一天结束的时候是否持有股票，0未持有，1持有
// @lc code=start
func maxProfit(prices []int) (ans int) {
	if len(prices) == 1 {
		return 0
	}
	dp := make([][]int, len(prices))
	for i := 0; i < len(prices); i++ {
		dp[i] = make([]int, 2)
	}
	dp[0][0] = 0
	dp[0][1] = -prices[0]
	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]) // 今天结束未持有股票，要么前一天未持有，要么今天卖了
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]) // 今天结束持有股票， 要么前一天就持有，要么今天买的
	}

	return dp[len(prices)-1][0]
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

// 2. 贪心
// 贪就贪在，【今天的股价-昨天的股价】，要么正数、要么0、要么负数，只加正数
// @lc code=start
func maxProfit(prices []int) (ans int) {
	for i := 1; i < len(prices); i++ {
		if prices[i]-prices[i-1] > 0 {
			ans += prices[i] - prices[i-1]
		}
	}
	return
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

// 1. 暴力超时（回溯） 198/200
// @lc code=start
func maxProfit(prices []int) (ans int) {
	var dfs func(flag bool, i, income int)
	dfs = func(flag bool, i, income int) { // flag:是否持有股票
		if i == len(prices) {
			ans = max(ans, income)
			return
		}
		dfs(flag, i+1, income) // 每一天有三种状态，【不操作，买入，卖出】
		if flag {
			dfs(false, i+1, income+prices[i])
		} else {
			dfs(true, i+1, income-prices[i])
		}
	}
	dfs(false, 0, 0)
	return
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

